#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
int selectmed(int *p,int s,int e)
{
	int i,j,k;
	int key,m;
	int *mp;
	int n=(e+1-s);
	mp=(int *)malloc((n+4)/5*sizeof(int));
	for(k=0;k<((e+1-s)+4)/5;k++)
	{
		for(i=k*5+1;i<(k+1)*5;i++)
		{
			if(i<(e+1-s))
			{
				key=p[i];
				j=i-1;
				while(j>=(k*5)&&p[j]>key)
				{
					p[j+1]=p[j];
					j=j-1;
				}
				p[j+1]=key;
			}
		}
		if((k+1)*5<=n) 
		{
			mp[k]=p[k*5+2];
		}
		else
		{
			mp[k]=p[(n-1-k*5)/2+k*5];
		}
	}
	if((n+4)/5==1) return mp[0];
	m=selectmed(mp,1,(n+4)/5);
	return m;
//	for(i=0;i<(n+4)/5;i++) printf("%d ",mp[i]);
	free(mp);
}


int partition(int *a,int p,int r,int m)
{
	int i,j,k;
	int temp,x;
	int q;
//	q=(r+p)/2;
	x=m;
	i=p;
	j=r;
	while(i<j)
	{
		while(a[i]<x) i++;
		while(a[j]>=x) j--;
		if(i<j)
		{
			temp=a[i];
			a[i]=a[j];
			a[j]=temp;
		}
	}
	return i;
}

int main()
{
	int i,j,k;
	int n,m;
	int *p;
	scanf("%d",&n);
	p=(int *)malloc(n*sizeof(int));
	for(i=0;i<n;i++) scanf("%d",&p[i]);
	m=selectmed(p,1,n);
	printf("median of medians is %d\n",m);
	for(i=0;i<n;i++) printf("%d ",p[i]);
	printf("\n");
	partition(p,0,n-1,m);
	for(i=0;i<n;i++) printf("%d ",p[i]);
	free(p);
}
